package com.c2b.algorithm.leetcode.jzoffer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * <a href="https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=13&&tqId=11182&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking">最小的K个数</a>
 * <p>给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。</p>
 * <p>例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。</p>
 * <p>数据范围：0≤k,n≤10000，数组中每个数的大小0 ≤ val ≤ 1000</p>
 * <p>要求：空间复杂度O(n) ，时间复杂度 O(nlogk)</p>
 *
 * @author c2b
 * @since 2023/3/8 14:34
 */
public class JzOffer0040GetLeastNumbers_S {
    /**
     * 大根堆(用Java优先队列实现)
     */
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k <= 0 || arr.length == 0 || k > arr.length) {
            return new int[0];
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>((Comparator.reverseOrder()));
        for (int i = 0; i < k; i++) {
            heap.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (heap.peek() > arr[i]) {
                heap.poll();
                heap.offer(arr[i]);
            }
        }
        int[] res = new int[k];
        int index = 0;
        while (!heap.isEmpty()) {
            res[index++] = heap.poll();
        }
        return res;
    }

    /**
     * 大根堆(用Java优先队列实现)
     */
    public ArrayList<Integer> GetLeastNumbers_Solution2(int[] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if (k <= 0 || input.length == 0 || k > input.length) {
            return res;
        }
        Arrays.sort(input);
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }
        return res;
    }


    public static void main(String[] args) {
        JzOffer0040GetLeastNumbers_S jzOffer0040GetLeastNumbers = new JzOffer0040GetLeastNumbers_S();
        int[] leastNumbers = jzOffer0040GetLeastNumbers.getLeastNumbers(new int[]{4, 5, 1, 6, 2, 7, 3, 8}, 4);
        for (Integer integer : leastNumbers) {
            System.out.println(integer);
        }
    }
}
